/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    typedef TreeNode node;
    bool FindPath(node* root, node* tar, vector<node*> &path)
    {
        if(!root) return 0;
        if(root->val==tar->val) {path.push_back(root); return 1;}
        bool l=FindPath(root->left, tar, path);
        bool r=FindPath(root->right, tar, path);
        if(l||r) path.push_back(root); //在当前路径中
        return l||r; //当前路径是否有效
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<node*> pathp, pathq;
        FindPath(root, p, pathp);
        FindPath(root, q, pathq);
        if(pathp.empty()||pathq.empty()) return nullptr;
        node* ans=nullptr;
        for(int i=0; i<min(pathp.size(), pathq.size()); i++)
        {
            if(pathp[pathp.size()-i-1]==pathq[pathq.size()-i-1]) ans=pathq[pathq.size()-i-1];
            
        }
        return ans;
    }
};